#include <iostream>
#include <vector>
using namespace std;

/*合并有序数组的问题解决了，
但我们排序时用的都是无序数组，那么上哪里去找这两个有序的数组呢？
*/

// 将 arr 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int>& arr, int start, int end) {
    int end1 = (start + end) / 2;
    int start2 = end1 + 1;
    // 用来遍历数组的指针
    int index1 = start;
    while (index1 <= end1 && start2 <= end) {
        if (arr[index1] > arr[start2]) {
            // 将 index1 和 start2 下标的数字交换
           swap(arr[index1], arr[start2]);
            if (start2 != end) {
                // 调整交换到 start2 上的这个数字的位置，使右边区域继续保持有序
                int value = arr[start2];
                int index = start2;
                // 右边区域比 arr[start2] 小的数字不断前移
                while (index < end && arr[index + 1] < value) {
                    arr[index] = arr[index + 1];
                    index++;
                }
                // 交换到右边区域的这个数字找到了自己合适的位置，坐下
                arr[index] = value;
            }
        }
        index1++;
    }
}

// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int>& arr, int start, int end) {
    // 只剩下一个数字，停止拆分
    if (start == end) return;
    int middle = (start + end) / 2;
    // 拆分左边区域
    mergeSort(arr, start, middle);
    // 拆分右边区域
    mergeSort(arr, middle + 1, end);
    // 合并左右区域
    merge(arr, start, end);
}
void mergeSort(vector<int>& arr) {
    if (arr.size() == 0) return;
    mergeSort(arr, 0, arr.size() - 1);
}


int main() {
	vector<int> v1{1,4,3,2,7,9,5,0,4,10,6,3};
	for(auto& t : v1)
		cout << t << " ";
	cout << endl;
	mergeSort(v1);
	//v = MergeSort2(v);
	for(auto& t : v1)
		cout << t << " ";
	cout << endl;
	return 0;
}
//我tm傻了